/**
* 小和问题，逆序对问题，使用分治的思想，对数器的模板
**/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#include<string.h>

//for test
int * generate_random_array(int max_size, int max_value) 
{
    srand((unsigned)time(NULL));
    int length = rand() % (max_size + 1); //生成0~maxSize+1的随机数
    int *const arr = (int*)malloc(length * sizeof(int));
	if(!arr)//如果malloc失败，可以得到一些log
	{
		perror("malloc");
		printf("generate_random_array\n");
		return NULL;
	}
    for (int i = 0; i < length; i++) {
        arr[i] = (rand() % (max_value + 1)) - (rand() % max_value);
    }
    return arr;
}

//for test
int* copy_array(const int * const arr, int length) 
{
	if (length == 0) {
		return NULL;
	}
	int *const res = (int *)malloc(length * sizeof(int));
	if(!res)//如果malloc失败，可以得到一些log
	{
		perror("malloc");
		printf("copy_array\n");
		return NULL;
	}
	for (int i = 0; i < length; i++) {
		res[i] = arr[i];
	}
	return res;
}

//for test
bool is_equal(int const arr1[], int length1, int const arr2[], int length2) 
{
    if ((length1 == 0 && length2 != 0) || (length1 != 0 && length2 == 0)) {
        return false;
    }
    if (length1 == 0 && length2 == 0) {
        return true;
    }
    if (length1 != length2) {
        return false;
    }
    for (int i = 0; i < length1; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}
//for test
void print_array(int const arr[], int length) {
    if (length == 0) {
        return;
    }
    for (int i = 0; i < length; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");
}

//poor fun
int poor(const int* const arr, int length)
{
    int res = 0;
    for (int i = 0; i < length -1; i++)
        for (int j = i + 1; j < length; j++) {
            res += arr[i] < arr[j]? arr[i]:0;
        }
    return res;
}

int conquer(int* const arr, int left, int mid, int right, int* const aux)
{
    int pl = left;
    int pr = mid + 1;
    int i = 0;
    int res = 0;
    while (pl <= mid && pr <= right) {
        res += arr[pl] < arr[pr]?(arr[pl]*(right - pr + 1)):0;
        aux[i++] = arr[pl] < arr[pr]? arr[pl++]:arr[pr++];
    }
    while (pl <= mid) aux[i++] = arr[pl++];
    while (pr <= right) aux[i++] = arr[pr++];
    for (int j = 0; j < (right - left + 1); j++)
        arr[left + j] = aux[j];

    return res;
}

int d_c(int* const arr, int left, int right, int * const aux)
{
    if (left == right) return 0;
    int mid = left + ((right - left) >> 1);
    
    return d_c(arr, left, mid, aux) + d_c(arr, mid + 1, right, aux)\
        + conquer(arr, left, mid, right, aux);
}

int new(int* const arr, int length)
{
    int *aux = (int*)malloc(length*sizeof(int));
    if (!aux) {
	    perror("malloc");
	    printf("conquer\n");
	    return -1;
    }
	memset(aux, 0, length*sizeof(int));
    if (arr == NULL || length < 2) return 0;
	int res = d_c(arr, 0, length - 1, aux); 
	if (aux) free(aux);
    aux = NULL;
	return res;   
    
} 
 
void main(int argc, char **argv) {
    int test_time = 500000;
    int max_size = 100;
    int max_value = 100;
    bool succeed = true;
    int *arr1 = NULL;
    int *arr2 = NULL;
    int new_res, poor_res;
    for (int i = 0; i < test_time; i++) {
        arr1 = generate_random_array(max_size, max_value);
        arr2 = copy_array(arr1, sizeof(arr1));
		poor_res = poor(arr1,sizeof(arr1));
        new_res = new(arr2, sizeof(arr2));

        if (new_res != poor_res) {
            succeed = false;
            break;
        }
		if (arr1) free(arr1); //当分配与释放不在一个函数，所有的系统调用都应该加上判断条件
		if (arr2) free(arr2); 
        arr1 = NULL; 
		arr2 = NULL; 
    }
    printf("%s\n", succeed ? "Nice!" : "Fucking fucked!");
    if (succeed == false) {
        printf("poor %d\n", poor_res);
        printf("qsort %d\n", new_res);
        printf("raw\n");
        print_array(arr1, sizeof(arr1));
    }

}